package main 

import (
	"fmt"

)

type Node struct{
	value  rune 
	weight int 
	lchild *Node
	rchild *Node
}

//Nodes 用于Node, 按照weight 排序
type Nodes []Node

//Tree 就是整棵Huffman树的根节点
type Tree struct{
	Root *Node
}


// 哈夫曼树
func main()  {
	a := Node{
		value: 'A',
		weight: 27,
	}

	b := Node{
		value: 'B',
		weight: 8,
	}
	c := Node{
		value: 'C',
		weight: 15,
	}
	d := Node{
		value: 'D',
		weight: 15,
	}
	e := Node{
		value: 'E',
		weight: 30,
	}

	f := Node{
		value: 'F',
		weight: 5,
	}

	nodes :=[]Node{a,b,c,d,e,f}
	// //按照权重排序
	// sorted := sortNodes(nodes);
	// //展示排序后的切片
	// showNodes(sorted);

	//生成哈夫曼树
	tree := makeHuffManTree(nodes);

	//中序遍历二叉树, 展示叶子结点
	root := tree.Root;
	showLeafNode(root)
}

//返回排好序的 Nodes
func  sortNodes(nodes Nodes)  (sorted []Node){
	for _, v := range nodes{
		
		
		if len(sorted) == 0{
			sorted = append(sorted, v);
		}else{
			i:=0;
			for   i<len(sorted) {
				if v.weight < sorted[i].weight {
					break;
				}
				i++
			}
			// 遍历完之后, 根据i的位置, 把v 插入到 temp当中
			if i==0{
				//头部插入元素
				// fmt.Println("元素插入到头部");
				temp := []Node{v}
				sorted =append(temp, sorted...);
			}else if i== len(sorted){
				//尾部插入元素
				// fmt.Println("元素插入到尾部");
				sorted = append(sorted, v);
			}else{
				//
				// fmt.Println("元素插入到中间位置");
				// fmt.Println("前半截", sorted[:i]);
				// fmt.Println("后半截", sorted[i:]);
				var pre  []Node;
				pre = append(pre, sorted[:i]...);

				var after  []Node
				after = append(after,  sorted[i:]...);

				//插入元素
				temp :=append(pre, v);

				sorted = append(temp, after...)
  			}
 
		}
		// fmt.Println("排序之后的切片:")
		// showNodes(sorted)
	}

	return sorted;
}

func  showNodes(nodes Nodes){
	for _, v := range nodes{
		fmt.Printf("value: %c,  weight: %d \n" ,v.value, v.weight)
	}
}

//返回哈夫曼树
func makeHuffManTree(nodes Nodes) *Tree{
	/*
		1 拿出权重最小的两个结点, a, b, 组成新结点; N1,N1的权重 =  a.weight + b.weight , 把N1 放到nodes 切片中

		2  在 nodes中再拿出两个权重最小的结点, 构成新树, 新树放回node中, 
		
		3  重复步骤2 ,  直到 nodes 中只剩一个结点,  则这个结点就是树的根节点  
	*/

 
	

	var root Node;
 	for  {
		if len(nodes) == 1{
			// 当 nodes中只有一个元素时,  这个元素必然是根元素
			break;
		}else{
			// 按照从权重小到大的顺序对 nodes进行排序, 这样, 取出的前两个就是权重最小的两个结点了
			nodes =  sortNodes(nodes);

			pre := nodes[:2];
			after := nodes[2:];
			// fmt.Println("pre", pre[0].weight, pre[1].weight)
			newNode := Node{}
			newNode.weight = pre[0].weight + pre[1].weight;
 
			newNode.lchild = &pre[0]
			newNode.rchild = &pre[1]

			//新结点放回到nodes中, 进入下一波循环 

			var temp  []Node;
			temp = append(temp, newNode)
			//生成的结点放入到 nodes 中
			nodes = append(temp, after...)

			// var left Node
			// var right Node
			
			// //权重小的放左边
			// if pre[0].weight < pre[1].weight{
			// 	left = pre[0]
			// 	right = pre[1]
			// }else{
			// 	left = pre[1]
			// 	right = pre[0]
			// }
	
			// fmt.Printf("左: %c 左边重 %d  右: %c  右边重: %d  新结点权重: %d \n", left.value, left.weight,  right.value, right.weight , newNode.weight)
	



		}
	}

	// for 循环结束后,  node中只有一个根元素 
	root = nodes[0];

	//打印根元素的权重
	// fmt.Println("root weight", root.weight);
	
	tree := &Tree{ Root: &root }
	return tree;
}

/**
遍历叶子结点
**/
func showLeafNode(node *Node)  {
	
	//左节点
	if node.lchild != nil{
		showLeafNode(node.lchild)
	}

	//右子节点
	if node.rchild != nil{
		showLeafNode(node.rchild)
	}

	//
	if node.lchild == nil  && node.rchild == nil {
		fmt.Printf("%c", node.value)
	}
}